import java.util.HashSet;
import java.util.Set;

public class Solution902 {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        Set<Integer> set=new HashSet<>();
        for (String digit : digits) {
            set.add(Integer.parseInt(digit));
        }
        int t=1,ans=0;
        long cur=9;
        while (n>=cur){
            int p=1;
            for (int i = 0; i < t; i++) {
                p=p*set.size();
            }
            ans=ans+p;
            cur=cur*10+9;
            t++;
            if (cur==t){
                return ans;
            }
        }
        ans+=dfs(String.valueOf(n),0,set,true);
        return ans;
    }

    private int dfs(String n, int k, Set<Integer> set, boolean limit) {
        if (k==n.length()){
            return 1;
        }
        if (!limit){
            return set.size()*dfs(n,k+1,set,false);
        }
        int ans=0;
        for (Integer integer : set) {
            if (integer < n.charAt(k)-'0'){
                ans+=dfs(n,k+1,set,false);
            }else if (integer==n.charAt(k)-'0'){
                ans+=dfs(n,k+1,set,true);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution902().atMostNGivenDigitSet(new String[]{"1","4","9"},1000000000));
    }
}
